<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            二分搜索树 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">二分搜索树</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2019-11-08 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E6%A0%91/">树</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>4.3k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>18 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <h2 id="二分搜索树"><a href="#二分搜索树" class="headerlink" title="二分搜索树"></a>二分搜索树</h2><p><strong>二叉查找树</strong>（英语：Binary Search Tree），也称为<strong>二分搜索树</strong>，<strong>二叉搜索树</strong>、<strong>有序二叉树</strong>（ordered binary tree）或<strong>排序二叉树</strong>（sorted binary tree）也可以简写为 <code>BST</code>，是指一棵空树或者具有下列性质的<a class="link"   target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91" >二叉树<i class="fas fa-external-link-alt"></i></a>：</p>
<ol>
<li>若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；</li>
<li>若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；</li>
<li>任意节点的左、右子树也分别为二叉查找树；</li>
<li>没有键值相等的节点。</li>
</ol>
<p>二叉查找树相比于其他数据结构的优势在于查找、插入的<a class="link"   target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6" >时间复杂度<i class="fas fa-external-link-alt"></i></a>较低。为<code>O(logN)</code>。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合，映射等</p>
<h2 id="基本结构"><a href="#基本结构" class="headerlink" title="基本结构"></a>基本结构</h2><p>先搭一个基本的架子出来，后面再来慢慢的完善功能</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">BST</span>&lt;<span class="title">E</span> <span class="keyword">extends</span> <span class="title">Comparable</span>&lt;<span class="title">E</span>&gt;&gt;</span>&#123;</span><br><span class="line">    <span class="comment">//TreeNode</span></span><br><span class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span></span>&#123;</span><br><span class="line">        <span class="keyword">public</span> E e;</span><br><span class="line">        <span class="keyword">public</span> Node left;</span><br><span class="line">        <span class="keyword">public</span> Node right;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(E e)</span></span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.e=e;</span><br><span class="line">            left=<span class="keyword">null</span>;</span><br><span class="line">            right=<span class="keyword">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> Node root;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> size;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">BST</span><span class="params">()</span></span>&#123;</span><br><span class="line">        root=<span class="keyword">null</span>;</span><br><span class="line">        size=<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> size;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> size==<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(E e)</span></span>&#123;</span><br><span class="line">        <span class="comment">//...</span></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">contains</span><span class="params">(E e)</span></span>&#123;</span><br><span class="line">        <span class="comment">//...</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="添加"><a href="#添加" class="headerlink" title="添加"></a>添加</h2><p>添加函数，时间复杂度<code>O(logN)</code>，只要抓住了它的性质就很好写，画个图描述下这个过程</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20191113/P39b50Ikv4sV.png?imageslim"
                      alt="mark"
                ></p>
<p>① 首先和root节点8比较，比8小，所以肯定再8的左子树中</p>
<p>② 再和root的左子树根节点5比较，比5大，所以最后肯定插入5的右子树中</p>
<p>③ 再和5节点的右子树根节点6比较，比6大，所以最后插入6的右子树中</p>
<p>④ 右子树为空，直接插入到6的右边</p>
<p>根据上面的流程我们很容易写出代码</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">addLoop</span><span class="params">(E e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root==<span class="keyword">null</span>) &#123;</span><br><span class="line">        size++;</span><br><span class="line">        root=<span class="keyword">new</span> Node(e);</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    Node temp=root;</span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span> (e.compareTo(temp.e)&gt;<span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (temp.right==<span class="keyword">null</span>) &#123;</span><br><span class="line">                temp.right=<span class="keyword">new</span> Node(e);</span><br><span class="line">                size++;</span><br><span class="line">                <span class="keyword">return</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            temp=temp.right;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span> (e.compareTo(temp.e)&lt;<span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (temp.left==<span class="keyword">null</span>) &#123;</span><br><span class="line">                temp.left=<span class="keyword">new</span> Node(e);</span><br><span class="line">                size++;</span><br><span class="line">                <span class="keyword">return</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            temp=temp.left;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">return</span>; <span class="comment">//不能有相等元素</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这里既然是树结构，用循环似乎有的显得不够优雅😂</p>
<p>所以我们尝试把这个改成递归</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add2</span><span class="params">(E e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(root == <span class="keyword">null</span>)&#123;</span><br><span class="line">        root = <span class="keyword">new</span> Node(e);</span><br><span class="line">        size ++;</span><br><span class="line">    &#125;<span class="keyword">else</span> add(root, e);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 向以node为根的二分搜索树中插入元素e,略显繁琐</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">add2</span><span class="params">(Node node, E e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(e.equals(node.e)) <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span>(e.compareTo(node.e) &lt; <span class="number">0</span> &amp;&amp; node.left == <span class="keyword">null</span>)&#123;</span><br><span class="line">        node.left = <span class="keyword">new</span> Node(e);</span><br><span class="line">        size ++;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(e.compareTo(node.e) &gt; <span class="number">0</span> &amp;&amp; node.right == <span class="keyword">null</span>)&#123;</span><br><span class="line">        node.right = <span class="keyword">new</span> Node(e);</span><br><span class="line">        size ++;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(e.compareTo(node.e) &lt; <span class="number">0</span>)</span><br><span class="line">        add(node.left, e);</span><br><span class="line">    <span class="keyword">else</span> <span class="comment">//e.compareTo(node.e) &gt; 0</span></span><br><span class="line">    	add(node.right, e);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这个递归？？？咋感觉比循环还繁琐🙄 </p>
<p>确实，上面这个递归的终止条件太繁琐了，<code>compareTo</code>一共比较了4次，有很多重复代码，所以我们还得改改😋</p>
<p>我们让这个<code>add</code>函数有返回值，返回插入后的根节点，这样我们的函数 <code>add(Node node,E e)</code> 定义就变成了 <strong>插入元素<code>e</code>到 以 <code>node</code> 为根节点的BST中，并且返回根节点</strong> ，清楚了递归函数的定义，我们再来写方法就会容易很多</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(E e)</span></span>&#123;</span><br><span class="line">    root=add(root,e);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//插入元素`e`到 以 `node` 为根节点的BST中，并且返回根节点</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> Node <span class="title">add</span><span class="params">(Node node, E e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (node == <span class="keyword">null</span>) &#123;</span><br><span class="line">        size++;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> Node(e);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(e.compareTo(node.e) &lt; <span class="number">0</span>)&#123;</span><br><span class="line">        <span class="comment">//插入左子树中，并返回根节点，然后接在node.left</span></span><br><span class="line">        node.left=add(node.left, e);</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span> (e.compareTo(node.e) &gt; <span class="number">0</span>) &#123; <span class="comment">//注意不要写else,前面没有对相等的元素做判断</span></span><br><span class="line">        <span class="comment">//插入右子树中，并返回根节点，然后接在node.right</span></span><br><span class="line">        node.right=add(node.right, e);   </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> node;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>还是那句话，写递归函数，不要纠结于函数的每一步是如何去进行，如何去得到结果的，从全局出发，只要搞清楚递归函数的定义，按照函数的定义来写代码，最后思考一下边界，最后的代码就一定是正确的！</p>
<p>这个边界的思考，其实也很简单，就比如上面的这个结束条件，我们不用去考虑一步步直到递归终结时是什么情况，我们思考一下极端的边界情况（其实这就是终结的情况），root为null，还没有初始化，BST还是空的，这个时候add元素，其实想都不用想，肯定是直接把这个 e作为根节点返回就ok了，所以很自然的就写出了终止条件</p>
<h2 id="查找"><a href="#查找" class="headerlink" title="查找"></a>查找</h2><p>查找相比于上面的添加，会简单很多，可以很容易的写出代码</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//查询操作</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">contains</span><span class="params">(E e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (e==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> contains(e,root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">contains</span><span class="params">(E e,Node root)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (e.compareTo(root.e)==<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> e.compareTo(root.e)&lt;<span class="number">0</span>?contains(e,root.left):contains(e,root.right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这里我为了简洁写了三目，不熟悉的可以改成if，整体时间复杂度依然是<code>O(logN)</code> ，比线性表的查找会快很多！</p>
<h2 id="遍历"><a href="#遍历" class="headerlink" title="遍历"></a>遍历</h2><p>老生常谈的话题，这个在我之前的 <a href="http://imlgw.top/2019/11/06/leetcode-er-cha-shu-di-gui/">LeetCode-二叉树</a> 里面也做过了，这里再翻出来看看，其实重点是想把后序遍历给搞清楚了，之前一直挺迷糊的</p>
<h3 id="前序遍历"><a href="#前序遍历" class="headerlink" title="前序遍历"></a>前序遍历</h3><h4 id="递归写法"><a href="#递归写法" class="headerlink" title="递归写法"></a>递归写法</h4><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//前序遍历,递归</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">preorderTravelRecur</span><span class="params">()</span></span>&#123;</span><br><span class="line">    preorderTravel(root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">preorderTravel</span><span class="params">(Node root)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    System.out.print(root.e+<span class="string">&quot; &quot;</span>);</span><br><span class="line">    preorderTravel(root.left);</span><br><span class="line">    preorderTravel(root.right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="非递归写法"><a href="#非递归写法" class="headerlink" title="非递归写法"></a>非递归写法</h4><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//前序遍历,非递归实现</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">preorderTravelNoRecur</span><span class="params">()</span></span>&#123;</span><br><span class="line">    Stack&lt;Node&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    Node cur=root;</span><br><span class="line">    <span class="keyword">while</span>( cur!=<span class="keyword">null</span> || !stack.isEmpty())&#123;</span><br><span class="line">        <span class="keyword">while</span>(cur!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            System.out.print(cur.e+<span class="string">&quot; &quot;</span>);</span><br><span class="line">            stack.push(cur);</span><br><span class="line">            cur=cur.left;</span><br><span class="line">        &#125;</span><br><span class="line">        cur=stack.pop();</span><br><span class="line">        cur=cur.right;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>注意这里并不是经典的前序遍历方式，是按照 “模板” 来的，首先我们考虑栈里面存的是什么，这里的栈里面存的实际上是 <code>左子树的左边</code> 的集合，这里我不知道咋描述，画个图吧</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20191113/BF0cCcWcy3zP.png?imageslim"
                      alt="mark"
                ></p>
<p>图中绿色部分就是我所说的<strong>左子树的左边的集合</strong>，整个栈的入栈顺序就是从左往右，从上到下，依次的将这些“左边” 入栈，并且在没有左子树，也就是遍历到叶子节点的时候开始出栈，然后切换成<code>当前出栈的节点</code>的右子树，将右子树的<code>左子树的左边</code>重复前面的过程继续入栈出栈，我们要考虑的就是在什么时候访问节点！</p>
<p>细心的同学肯定已经发现了，其实这里进栈顺序和出栈顺序，分别对应的就是这颗树前序遍历和中序遍历！！！所以我们就只需要在进栈和出栈的时候，进行访问节点的操作，就可以完成前序和后序遍历</p>
<h3 id="中序遍历"><a href="#中序遍历" class="headerlink" title="中序遍历"></a>中序遍历</h3><h4 id="递归写法-1"><a href="#递归写法-1" class="headerlink" title="递归写法"></a>递归写法</h4><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//中序遍历,递归</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">inorderTravelRecur</span><span class="params">()</span></span>&#123;</span><br><span class="line">    inorderTravel(root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">inorderTravel</span><span class="params">(Node root)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    inorderTravel(root.left);</span><br><span class="line">    System.out.print(root.e+<span class="string">&quot; &quot;</span>);</span><br><span class="line">    inorderTravel(root.right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="非递归写法-1"><a href="#非递归写法-1" class="headerlink" title="非递归写法"></a>非递归写法</h4><p>结合上面的分析，我们也可以很容易的得出非递归的中序遍历的写法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//中序遍历,非递归</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">inorderTravelNoRecur</span><span class="params">()</span></span>&#123;</span><br><span class="line">    Stack&lt;Node&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    Node cur=root;</span><br><span class="line">    <span class="keyword">while</span>( cur!=<span class="keyword">null</span> || !stack.isEmpty())&#123;</span><br><span class="line">        <span class="keyword">while</span>(cur!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            stack.push(cur);</span><br><span class="line">            cur=cur.left;</span><br><span class="line">        &#125;</span><br><span class="line">        cur=stack.pop();</span><br><span class="line">        System.out.print(cur.e+<span class="string">&quot; &quot;</span>);</span><br><span class="line">        cur=cur.right;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="后序遍历"><a href="#后序遍历" class="headerlink" title="后序遍历"></a>后序遍历</h3><h4 id="递归写法-2"><a href="#递归写法-2" class="headerlink" title="递归写法"></a>递归写法</h4><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//后序遍历,递归</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">postorderTravelRecur</span><span class="params">()</span></span>&#123;</span><br><span class="line">    postorderTravel(root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">postorderTravel</span><span class="params">(Node root)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    postorderTravel(root.left);</span><br><span class="line">    postorderTravel(root.right);</span><br><span class="line">    System.out.print(root.e+<span class="string">&quot; &quot;</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="非递归写法-2"><a href="#非递归写法-2" class="headerlink" title="非递归写法"></a>非递归写法</h4><p>这里的非递归写法就不一样了，比前两种要复杂</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//后序遍历,非递归</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">postorderTravelNoRecur</span><span class="params">()</span></span>&#123;</span><br><span class="line">    Stack&lt;Node&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    Node cur=root,lastNode=<span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">while</span>(cur!=<span class="keyword">null</span> || !stack.isEmpty())&#123;</span><br><span class="line">        <span class="keyword">while</span>(cur!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            stack.push(cur);</span><br><span class="line">            cur=cur.left;</span><br><span class="line">        &#125;</span><br><span class="line">        cur=stack.peek();<span class="comment">//查看栈顶元素</span></span><br><span class="line">        <span class="comment">//如果右子树为空或者右节点已经访问过，则当前节点出栈，并记录lastNode</span></span><br><span class="line">        <span class="keyword">if</span> (cur.right==<span class="keyword">null</span> || lastNode==cur.right) &#123; </span><br><span class="line">            System.out.print(cur.e+<span class="string">&quot; &quot;</span>);</span><br><span class="line">            stack.pop();</span><br><span class="line">            lastNode=cur;</span><br><span class="line">            <span class="comment">//为了下一次能直接查看栈顶元素</span></span><br><span class="line">            <span class="comment">//cur的使命其实已经结束了，cur和它的孩子都已经访问了，下一次直接从栈顶取，不然就死循环了</span></span><br><span class="line">            cur=<span class="keyword">null</span>; </span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            cur=cur.right;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20191113/zM80igBy0RDX.png?imageslim"
                      alt="mark"
                ></p>
<p>其实不管是什么遍历，对于这个模板来说，<strong>栈的轨迹都是一样的</strong>，只不过访问节点的时机有所不同，蓝色线条代表审查的顺序，红色辅助的代表出栈部分，右边对应的就是遍历过程中栈的变化，和对应结果的变化，对照这个图再分析下就很清楚了。</p>
<p>如果觉得实在是不好理解也可以换用下面的方式</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">postorderTravelNoRecur2</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    Stack&lt;Node&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    stack.push(root);</span><br><span class="line">    Node lastNode=<span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">while</span>(!stack.isEmpty())&#123;</span><br><span class="line">        <span class="comment">//取栈顶元素</span></span><br><span class="line">        Node cur=stack.peek();</span><br><span class="line">        <span class="comment">//左右子树都为空，或者上一个访问的节点是当前节点的子节点就输出该节点</span></span><br><span class="line">        <span class="keyword">if</span> ( (cur.left==<span class="keyword">null</span> &amp;&amp; cur.right ==<span class="keyword">null</span>) || </span><br><span class="line">             (lastNode!=<span class="keyword">null</span> &amp;&amp;(cur.left==lastNode || cur.right==lastNode)))&#123;</span><br><span class="line">            stack.pop();</span><br><span class="line">            System.out.print(cur.e+<span class="string">&quot; &quot;</span>);</span><br><span class="line">            lastNode=cur;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">if</span> (cur.right!=<span class="keyword">null</span>) &#123;</span><br><span class="line">                stack.push(cur.right);</span><br><span class="line">            &#125; <span class="keyword">if</span> (cur.left!=<span class="keyword">null</span>) &#123;</span><br><span class="line">                stack.push(cur.left);</span><br><span class="line">            &#125;  </span><br><span class="line">        &#125; </span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这种方式相比上面就好理解多了，左右子树都为空，或者上一个访问的节点是当前节点的子节点，就可以输出该节点了，注意添加的时候是逆序添加的，这样就可以保证先访问左节点，再访问右节点，最后访问根节点</p>
<h3 id="层次遍历"><a href="#层次遍历" class="headerlink" title="层次遍历"></a>层次遍历</h3><h4 id="递归写法-3"><a href="#递归写法-3" class="headerlink" title="递归写法"></a>递归写法</h4><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> List&lt;List&lt;Integer&gt;&gt; levelOrder(TreeNode root) &#123;</span><br><span class="line">    List&lt;List&lt;Integer&gt;&gt; res = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    helper(res, root, <span class="number">0</span>);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">helper</span><span class="params">(List&lt;List&lt;Integer&gt;&gt; res, TreeNode root, <span class="keyword">int</span> depth)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root == <span class="keyword">null</span>) <span class="keyword">return</span>;</span><br><span class="line">    <span class="comment">//需要增加一层</span></span><br><span class="line">    <span class="keyword">if</span> (res.size() == depth) res.add(<span class="keyword">new</span> LinkedList&lt;&gt;());</span><br><span class="line">    res.get(depth).add(root.val);</span><br><span class="line">    helper(res, root.left, depth + <span class="number">1</span>);</span><br><span class="line">    helper(res, root.right, depth + <span class="number">1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="非递归写法-3"><a href="#非递归写法-3" class="headerlink" title="非递归写法"></a>非递归写法</h4><p>经典的BFS</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//层次遍历</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">levelorderTravel</span><span class="params">()</span></span>&#123;</span><br><span class="line">    Queue&lt;Node&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    queue.add(root);</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        <span class="keyword">int</span> count=queue.size();</span><br><span class="line">        <span class="keyword">while</span>(count&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            Node node=queue.poll();</span><br><span class="line">            System.out.print(node.e+<span class="string">&quot; &quot;</span>);</span><br><span class="line">            <span class="keyword">if</span> (node.left!=<span class="keyword">null</span>) &#123;</span><br><span class="line">                queue.add(node.left);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (node.right!=<span class="keyword">null</span>) &#123;</span><br><span class="line">                queue.add(node.right);</span><br><span class="line">            &#125;</span><br><span class="line">            count--;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<blockquote>
<p>其实关于前中后序的遍历方式，还有很多，我这里主要记录的是<code>模板</code>的思路，其实还有一种很🐂🍺的做法，模拟系统栈的方式，具体可以参考我之前的  <a href="http://imlgw.top/2019/11/06/leetcode-er-cha-shu-di-gui/#144-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86">LeetCode二叉树</a> 这里就不多解释了</p>
</blockquote>
<h2 id="取整"><a href="#取整" class="headerlink" title="取整"></a>取整</h2><h3 id="向下取整（floor）"><a href="#向下取整（floor）" class="headerlink" title="向下取整（floor）"></a>向下取整（floor）</h3><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> E <span class="title">floor</span><span class="params">(E e)</span></span>&#123;</span><br><span class="line">    Node node=floor(root,e);</span><br><span class="line">    <span class="keyword">return</span> node!=<span class="keyword">null</span>?node.e:<span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> Node <span class="title">floor</span><span class="params">(Node root,E e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> temp=e.compareTo(root.e);</span><br><span class="line">    <span class="keyword">if</span> (temp==<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (temp&lt;<span class="number">0</span>) &#123; <span class="comment">//root.e &gt; e,求小于e的值,一定在左边</span></span><br><span class="line">        <span class="keyword">return</span> floor(root.left,e);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//tmep&gt;0 e&gt;root.e</span></span><br><span class="line">    Node node=floor(root.right,e);</span><br><span class="line">    <span class="keyword">return</span> node!=<span class="keyword">null</span>?node:root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="向上取整（ceiling）"><a href="#向上取整（ceiling）" class="headerlink" title="向上取整（ceiling）"></a>向上取整（ceiling）</h3><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> E <span class="title">ceiling</span><span class="params">(E e)</span></span>&#123;</span><br><span class="line">    Node node=ceiling(root,e);</span><br><span class="line">    <span class="keyword">return</span> node!=<span class="keyword">null</span>?node.e:<span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> Node <span class="title">ceiling</span><span class="params">(Node root,E e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> temp=e.compareTo(root.e);</span><br><span class="line">    <span class="keyword">if</span> (temp==<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (temp&gt;<span class="number">0</span>) &#123; <span class="comment">//root.e&lt;e,求的是最后大于root.e的元素,一定在右边</span></span><br><span class="line">        <span class="keyword">return</span> ceiling(root.right,e);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//tmep&lt;0 e&lt;root.e</span></span><br><span class="line">    Node node=ceiling(root.left,e);</span><br><span class="line">    <span class="keyword">return</span> node!=<span class="keyword">null</span>?node:root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这两个函数还是挺有用的，比如这个题 <a href="http://imlgw.top/2019/09/15/leetcode-cha-zhao/#220-%E5%AD%98%E5%9C%A8%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0-III">220-存在重复元素-III </a> 通过率只有25%的mid题。。。。</p>
<h2 id="获取第K大"><a href="#获取第K大" class="headerlink" title="获取第K大"></a>获取第K大</h2><p>获取第k大（从0开始）的元素，如果左子树节点数小于<code>k</code>，则第k大的元素肯定在右子树，同时我们可以直接排除<code>size(left)+1</code> 个元素（加上根节点） 。</p>
<p>然后直接在 右子树中继续搜索 <code>getKth(root.right,k-size(left)-1)</code>  ，只有当左子树刚好k个元素的时候，根节点就是我们要找的<code>Kth</code></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> E <span class="title">getKth</span><span class="params">(<span class="keyword">int</span> k)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (k&gt;=size || k&lt;<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> getKth(root,k).e;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> Node <span class="title">getKth</span><span class="params">(Node root,<span class="keyword">int</span> k)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> temp = childSize(root.left);</span><br><span class="line">    <span class="keyword">if</span> (temp&gt;k) &#123;</span><br><span class="line">        <span class="keyword">return</span> getKth(root.left,k);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (temp&lt;k) &#123;</span><br><span class="line">        <span class="keyword">return</span> getKth(root.right,k-temp-<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<blockquote>
<p>这里其实我的实现是有问题的，我的时间复杂度是<code>O(NlogN)</code>！！！！主要是<code>childSize()</code>时间复杂度是O(N)不是O(1)，在《算法4》中这个实现的时间复杂度就是O(1)，书上在定义的Node的时候给Node加了一个count属性，用来记录每个节点的子节点数（包括自己），在每次add和delete的时候动态的维护这个count，这样最后求子节点数的操作时间复杂度就是O(1)的了，那个版本的我也实现了一下，但是我没有在这篇文章中这样写（主要是懒得改），而且这也不是重点，感兴趣可以去看看 <a class="link"   target="_blank" rel="noopener" href="https://github.com/imlgw/LeetCode/blob/master/tree/BSTWithCount.java" >BSTWithCount<i class="fas fa-external-link-alt"></i></a> 主要就是要<strong>注意操作count的时机</strong></p>
</blockquote>
<p>这里既然没有count数组，那么其实就不应该这样求，应该直接中序遍历，求第K大，时间复杂度O(N)</p>
<h2 id="Rank"><a href="#Rank" class="headerlink" title="Rank()"></a>Rank()</h2><p>其实是上面的逆过程，如果根节点等于key，那么直接返回左子树的键总数；如果key小于根节点，就继续去左子树中递归找，如果大于根节点，返回<code>size(left)+1</code>加上它在右子树中的<code>rank()</code></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getRank</span><span class="params">(E e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> getRank(root,e);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getRank</span><span class="params">(Node root,E e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (e.compareTo(root.e)&lt;<span class="number">0</span>) &#123; <span class="comment">//e&lt;root.e</span></span><br><span class="line">        <span class="keyword">return</span> getRank(root.left,e);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (e.compareTo(root.e)&gt;<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> getRank(root.right,e)+childSize(root.left)+<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> childSize(root.left);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="Max-amp-Min"><a href="#Max-amp-Min" class="headerlink" title="Max&amp;Min"></a>Max&amp;Min</h2><p>没啥好说的</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//求最大值,递归比较优雅</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> E <span class="title">getMax</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> getMax(root).e;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> Node <span class="title">getMax</span><span class="params">(Node root)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root.right==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> getMax(root.right);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//求最小值</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> E <span class="title">getMin</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> getMin(root).e;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> Node <span class="title">getMin</span><span class="params">(Node root)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root.left==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> getMin(root.left);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h2><p>删除应该来说是BST中里面比较复杂的一个操作了，我们先从简单的开始</p>
<h3 id="删除最值"><a href="#删除最值" class="headerlink" title="删除最值"></a>删除最值</h3><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//删除最小的键</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">deleteMin</span><span class="params">()</span></span>&#123;</span><br><span class="line">    root=deleteMin(root);</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//删除node为头节点的树中的最小值，并返回头节点</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> Node <span class="title">deleteMin</span><span class="params">(Node node)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (node.left==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> node.right;</span><br><span class="line">    &#125;</span><br><span class="line">    node.left=deleteMin(node.left);</span><br><span class="line">    <span class="keyword">return</span> node;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//删除最大的键</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">deleteMax</span><span class="params">()</span></span>&#123;</span><br><span class="line">    root=deleteMax(root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> Node <span class="title">deleteMax</span><span class="params">(Node node)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (node.right==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> node.left;</span><br><span class="line">    &#125;</span><br><span class="line">    node.right=deleteMax(node.right);</span><br><span class="line">    <span class="keyword">return</span> node;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>递归函数定义为<strong>删除node为头节点的树中的最小值，并返回头节点</strong>，删除最小值实际上就是删除二叉树最左边的节点，所以我们递归的删除node.left就ok，当node.left为空的时候返回node.right，这样前面节点的left就接在了node.right上，就达到了删除的作用</p>
<h3 id="删除任意值"><a href="#删除任意值" class="headerlink" title="删除任意值"></a>删除任意值</h3><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//删除任意的键</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">delete</span><span class="params">(E e)</span></span>&#123;</span><br><span class="line">    root=delete(root,e);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//删除以node为首的BST中,值为e的节点并且返回根节点</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> Node <span class="title">delete</span><span class="params">(Node node,E e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (node==<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (e.compareTo(node.e)&gt;<span class="number">0</span>) &#123; <span class="comment">//e&gt;root.e</span></span><br><span class="line">        node.right=delete(node.right,e);</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span> (e.compareTo(node.e)&lt;<span class="number">0</span>) &#123;</span><br><span class="line">        node.left=delete(node.left,e);</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123; <span class="comment">//e==root.e</span></span><br><span class="line">        <span class="keyword">if</span> (node.left==<span class="keyword">null</span>) &#123; <span class="comment">//如果没有左子树就返回右子树</span></span><br><span class="line">            <span class="keyword">return</span> node.right;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (node.right==<span class="keyword">null</span>) &#123; <span class="comment">//如果没有右子树就返回左子树</span></span><br><span class="line">            <span class="keyword">return</span> node.left;</span><br><span class="line">        &#125;</span><br><span class="line">        Node delNode=node;</span><br><span class="line">        <span class="comment">//有左右子节点都有</span></span><br><span class="line">        node=getMin(node.right); <span class="comment">//用右子树的最小值填补删除的元素的空位</span></span><br><span class="line">        <span class="comment">//删除对应的右子树的最小值,然后连接起来</span></span><br><span class="line">        node.right=deleteMin(delNode.right);</span><br><span class="line">        node.left=delNode.left;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> node;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这里文字的描述比较无力，画个图就清晰明白了，核心的思想就是利用右子树中的最小值填补待删除节点</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20191113/yyI0q2yftm0X.png?imageslim"
                      alt="mark"
                ></p>
<p>当然这里其实也是有坑的，主要就是连最后两句</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//删除对应的右子树的最小值,然后连接起来</span></span><br><span class="line">node.right=deleteMin(delNode.right);</span><br><span class="line">node.left=delNode.left;</span><br></pre></td></tr></table></figure>
<p>这里的两句话是不能交换的，如果我们交换了两句话的位置，那么我们下一步删除最小值就会出现问题，我们希望的是删除右子树中最小的node节点，结果你先把待删除节点的left接到了node的左边，这样的话node就不再是delNode.right中的最小值，最后结果可能就会成这个样子，成了一个闭环！！！</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20191113/qc5kHljj03uq.png?imageslim"
                      alt="mark"
                ></p>
<p>所以最后的结果肯定是不对的，其实这一点书上并没有提到，我也是在做这道题<a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/delete-node-in-a-bst/" >删除节点<i class="fas fa-external-link-alt"></i></a> 的时候写反了，才发现这个问题，感兴趣可以去试试</p>
<blockquote>
<p>其实这样的删除时一种很随机的做法，虽然能正确的删除元素，但是并没有考虑树的对称性，关于树的对称性，我们后面再来研究</p>
</blockquote>
<h2 id="代码地址"><a href="#代码地址" class="headerlink" title="代码地址"></a>代码地址</h2><p><a class="link"   target="_blank" rel="noopener" href="https://github.com/imlgw/LeetCode/blob/master/tree/BST.java" >BST.java<i class="fas fa-external-link-alt"></i></a></p>
<p><a class="link"   target="_blank" rel="noopener" href="https://github.com/imlgw/LeetCode/blob/master/tree/BSTTest.java" >BSTTest.java<i class="fas fa-external-link-alt"></i></a></p>
<p><a class="link"   target="_blank" rel="noopener" href="https://github.com/imlgw/LeetCode/blob/master/tree/BSTWithCount.java" >BSTWithCount.java<i class="fas fa-external-link-alt"></i></a></p>

        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：二分搜索树</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2019-11-08 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2019/11/08/a49b5008/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2019/11/16/c0884f64/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">LRU队列实现</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2019/11/06/43c532c9/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">LeetCode二叉树</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2019/11/08/a49b5008/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E6%A0%91"><span class="nav-number">1.</span> <span class="nav-text">二分搜索树</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%9F%BA%E6%9C%AC%E7%BB%93%E6%9E%84"><span class="nav-number">2.</span> <span class="nav-text">基本结构</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%B7%BB%E5%8A%A0"><span class="nav-number">3.</span> <span class="nav-text">添加</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%9F%A5%E6%89%BE"><span class="nav-number">4.</span> <span class="nav-text">查找</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%81%8D%E5%8E%86"><span class="nav-number">5.</span> <span class="nav-text">遍历</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86"><span class="nav-number">5.1.</span> <span class="nav-text">前序遍历</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%80%92%E5%BD%92%E5%86%99%E6%B3%95"><span class="nav-number">5.1.1.</span> <span class="nav-text">递归写法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%9D%9E%E9%80%92%E5%BD%92%E5%86%99%E6%B3%95"><span class="nav-number">5.1.2.</span> <span class="nav-text">非递归写法</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86"><span class="nav-number">5.2.</span> <span class="nav-text">中序遍历</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%80%92%E5%BD%92%E5%86%99%E6%B3%95-1"><span class="nav-number">5.2.1.</span> <span class="nav-text">递归写法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%9D%9E%E9%80%92%E5%BD%92%E5%86%99%E6%B3%95-1"><span class="nav-number">5.2.2.</span> <span class="nav-text">非递归写法</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86"><span class="nav-number">5.3.</span> <span class="nav-text">后序遍历</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%80%92%E5%BD%92%E5%86%99%E6%B3%95-2"><span class="nav-number">5.3.1.</span> <span class="nav-text">递归写法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%9D%9E%E9%80%92%E5%BD%92%E5%86%99%E6%B3%95-2"><span class="nav-number">5.3.2.</span> <span class="nav-text">非递归写法</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%B1%82%E6%AC%A1%E9%81%8D%E5%8E%86"><span class="nav-number">5.4.</span> <span class="nav-text">层次遍历</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%80%92%E5%BD%92%E5%86%99%E6%B3%95-3"><span class="nav-number">5.4.1.</span> <span class="nav-text">递归写法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%9D%9E%E9%80%92%E5%BD%92%E5%86%99%E6%B3%95-3"><span class="nav-number">5.4.2.</span> <span class="nav-text">非递归写法</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%8F%96%E6%95%B4"><span class="nav-number">6.</span> <span class="nav-text">取整</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%90%91%E4%B8%8B%E5%8F%96%E6%95%B4%EF%BC%88floor%EF%BC%89"><span class="nav-number">6.1.</span> <span class="nav-text">向下取整（floor）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%90%91%E4%B8%8A%E5%8F%96%E6%95%B4%EF%BC%88ceiling%EF%BC%89"><span class="nav-number">6.2.</span> <span class="nav-text">向上取整（ceiling）</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%8E%B7%E5%8F%96%E7%AC%ACK%E5%A4%A7"><span class="nav-number">7.</span> <span class="nav-text">获取第K大</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Rank"><span class="nav-number">8.</span> <span class="nav-text">Rank()</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Max-amp-Min"><span class="nav-number">9.</span> <span class="nav-text">Max&amp;Min</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%88%A0%E9%99%A4"><span class="nav-number">10.</span> <span class="nav-text">删除</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%88%A0%E9%99%A4%E6%9C%80%E5%80%BC"><span class="nav-number">10.1.</span> <span class="nav-text">删除最值</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%88%A0%E9%99%A4%E4%BB%BB%E6%84%8F%E5%80%BC"><span class="nav-number">10.2.</span> <span class="nav-text">删除任意值</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BB%A3%E7%A0%81%E5%9C%B0%E5%9D%80"><span class="nav-number">11.</span> <span class="nav-text">代码地址</span></a></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
